The present invention relates to a cell output contention control apparatus for a traffic shaper and, more particularly, to a traffic shaper cell output contention control apparatus used to output cells onto virtual paths or channels set on an ATM (Asynchronous Transfer Mode) transmission line by a traffic shaper while averaging transmission intervals.
In an ATM network, when cells are to be output to a plurality of virtual paths or channels multiplexed on a transmission line, a traffic with high burstiness is generally input. Even in this case, a traffic shaper is used to average cell transmission intervals with respect to one virtual path or channel so as to prevent the number of cells to be transmitted from exceeding the transmission capacity of each virtual path or channel.
This traffic shaper determines the ideal transmission time of each arrival cell on the basis of a predetermined algorithm such that the cell transmission intervals become equal intervals. Cells are temporarily stored in a delaying cell memory (buffer), and the respective cells are sequentially transmitted at the corresponding transmission times. As a method of managing the transmission order of cells, a method of assigning actual transmission times to the respective time slots of the memory is available.
In this method, cells or their addresses of the cell memory are stored in the time slots of the memory which have the same transmission times as the ideal transmission times of the respective cells, the cell or its storage address stored in the time slot corresponding to the current time is sequentially read out, and the cell or the cell stored at the cell storage address is transmitted, thereby managing the cell transmission order.
According to this method, if the same ideal transmission times are calculated with respect to a plurality of cells which have arrived at different times, the ideal transmission time of a cell which has arrived at a given time may contend against that of a cell which had already arrived (in the past). In addition, if the actual transmission time of a given cell is changed to a time different from the ideal transmission time by cell transmission contention control, the ideal transmission time of a cell which has arrived at the given time may contend against the actual transmission time of the cell which had already arrived (in the past).
If such contention occurs, cell output contention control needs to be performed. For example, the actual transmission time of a cell which has arrived later is delayed (in the future) with respect to the ideal transmission time of the cell.
As such a control method, a conventional cell output contention control method has been proposed (for example, "Spacing Cells Protects and Enhances Utilization of ATM Network Links", IEEE Network, pp. 38-49, September, 1992), in which when output contention occurs with respect to a time slot corresponding to the ideal transmission time of an arrival cell, an available time slot which is later than the time slot indicated by the ideal transmission time and is not used is searched out, and the arrival cell or its address is stored in the found available time slot.
This output contention control method uses an available time slot search method in which a time slot corresponding to the ideal transmission time of an arrival cell is set as a search start slot, and the use states of the respective time slots are sequentially checked in the direction of the future, starting from the search start slot, until an available time slot is searched out because of the necessity to hold the cell transmission order on a single virtual path or channel.
In the output contention control apparatus for such a conventional traffic shaper, however, since time slots are sequentially searched from a search start slot in the direction of the future to search out an available time slot in which an arrival cell is to be stored, the use states of all the time slots to be searched cannot be checked within a 1-cell time until the next cell arrives, provided that a cell transmission rate is high or a transmission order management memory has a large capacity.
If the available time slot search range is limited in accordance with the transmission rate of cells, the capacity of the transmission order management memory is limited. As a result, no available time slot may be found, and a cell loss may occur.